# 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
# 输出：[1,2,4,7,5,3,6,8,9]
#  
# 
#  示例 2： 
# 
#  
# 输入：mat = [[1,2],[3,4]]
# 输出：[1,2,3,4]
#  
# 
#  
# 
#  提示： 
# 
#  
#  m == mat.length 
#  n == mat[i].length 
#  1 <= m, n <= 10⁴ 
#  1 <= m * n <= 10⁴ 
#  -10⁵ <= mat[i][j] <= 10⁵ 
#  
# 
#  Related Topics 数组 矩阵 模拟 👍 503 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m = len(mat)
        n = len(mat[0])
        i = j = 0
        re = [mat[0][0]]
        while len(re)!=m*n:
            while 0 <= i - 1 < m and 0 <= j + 1 < n:
                # 如果右上有格子，则向右上移
                i = i - 1
                j = j + 1
                re.append(mat[i][j])
            # 右上没有格子，向右移动
            j = j + 1
            if 0 <= i < m and 0 <= j < n:
                re.append(mat[i][j])

            while 0 <= i + 1 < m and 0 <= j - 1 < n:
                # 如果左下有格子，则向坐下移
                i = i + 1
                j = j - 1
                re.append(mat[i][j])
            # 右上没有格子，向下移动
            i = i + 1
            if 0 <= i < m and 0 <= j < n:
                re.append(mat[i][j])
        return re


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().findDiagonalOrder(mat=[[2,3]]))
